package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;

/**
 * 寻找模节点，即：从链表表头开始找到最后一个满足 i%k==0 的节点
 * @author zifangsky
 *
 */
public class Problem_015_FindModeNode {
	
	/**
	 * 思路：略
	 * @时间复杂度 O(n)
	 * @param headNode
	 * @param k
	 * @return
	 */
	public SinglyNode getModularNode(SinglyNode headNode,int k){
		SinglyNode result = null;
		if(k <= 0){
			return null;
		}
		
		for(int i=1;headNode!=null;i++){
			if(i % k == 0){
				result = headNode;
			}
			headNode = headNode.getNext();	
		}
		return result;
	}

	@Test
	public void testMethods(){
		SinglyNode headNode = new SinglyNode(1);
		
		SinglyNode currentNode = headNode;
		for(int i=2;i<=7;i++){
			SinglyNode tmpNode = new SinglyNode(i);
			currentNode.setNext(tmpNode);
			currentNode = tmpNode;
		}
		
		//遍历初始链接
		SinglyNodeOperations.print(headNode);
		
		System.out.println("目标节点是： " + getModularNode(headNode,3));
	}
	
}
